package 二分查找;
import java.util.*;
/**
 * 该类用于在有序数组中查找目标值的插入位置。
 * 时间复杂度：O(log n)，空间复杂度：O(1)
 */
public class searchInsert {
    /**
     * 在有序数组中查找目标值的插入位置。
     * 该方法使用二分查找算法，通过比较中间元素与目标值来确定插入位置。
     * @param nums 有序数组
     * @param target 目标值
     * @return 目标值在数组中的插入位置
     */
    public int searchIns(int[] nums, int target) {
        int left = 0; // 左边界
        int right = nums.length - 1; // 右边界
        while(left <= right) { // 当左边界小于等于右边界时继续循环
            int mid = (left + right) >> 1; // 计算中间索引
            if(nums[mid] > target) right = mid - 1; // 如果中间元素大于目标值，更新右边界
            else if(nums[mid] < target) left = mid + 1; // 如果中间元素小于目标值，更新左边界
            else return mid; // 如果找到目标值，返回索引
        }
        return left; // 返回插入位置
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取数组和目标值，并输出目标值在数组中的插入位置。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s = sc.nextLine().split(","); // 读取数组
        int[] nums = new int[s.length]; // 创建数组
        int target = sc.nextInt(); // 读取目标值
        for(int i = 0; i < s.length; i++) {
            nums[i] = Integer.parseInt(s[i]); // 解析数组
        }
        searchInsert si = new searchInsert(); // 创建对象
        System.out.println(si.searchIns(nums, target)); // 输出目标值在数组中的插入位置
        sc.close(); // 关闭扫描器
    }
}
